package com.qch.leecode.cyc2018.algorithm.a1_double_pointer;

/**
 * 算法思想：双指针：680. 验证回文串 II
 * https://leetcode.cn/problems/valid-palindrome-ii/
 * 自己思路缺点：纠结好久没做出来
 *
 * @Author qch
 * @Date 2022/11/7
 *
 * 题目：给你一个字符串 s，最多 可以从中删除一个字符。
 * 请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false
 *
 *输入：s = "aba"
 * 输出：true
 *
 * 输入：s = "abca"
 * 输出：true
 * 解释：你可以删除字符 'c'
 *
 * 输入：s = "abc"
 * 输出：false
 *
 * 解题思路注意：题目理解错误aba不用删除也是回文
 */
public class L4_PalindromeString680 {
    public static void main(String[] args) {
        boolean str = good_validPalindrome("aabcda");
        //boolean str1 = own_validPalindrome("aba");
        System.out.println(str);
    }
    public static boolean good_validPalindrome(String c) {

        for (int i=0, j= c.length()-1; i <j ; i++,j--) {
            if(c.charAt(i)!=c.charAt(j))
            {
                //最外边不相等，先比i,j--,再比i++,j,只要有一个满足回文就成功
                return isPalindrome(c,i,j-1)||isPalindrome(c,i+1,j);
            }
        }
        return true;
    }

    private static boolean isPalindrome(String sonstr,int i,int j)
    {
        //因为i=j的时候已经退出，所以当bab时，是true
        //因为在外层已经出现一次不等，内层再出现一次就代表不是回文
        while (i<j) {
            if (sonstr.charAt(i++) != sonstr.charAt(j--)) {
                return false;
            }
        }
        return true;
    }
    /**
     * 247 / 469
     * 题目理解错误aba不用删除也是回文
     * @param c
     * @return
     */
    public static boolean error_under_own_validPalindrome(String c) {
        int i=0;
        int j=c.length()-1;
        boolean flag=true;
        int delcount=0;
        while (i<j&&delcount<=1)
        {
            char ci=c.charAt(i);
            char cj=c.charAt(j);
            if(ci==cj){
                i++;
                j--;
            }else {
                if(i+1==j){
                    return false;
                }
                if(c.charAt(++i)==cj)
                {
                    delcount++;
                    i++;
                    j--;
                }else if(c.charAt(--j)==ci){
                    delcount++;
                    i++;
                    j--;
                }else {
                    return false;
                }
            }
        }
        if(delcount>1)
            return false;
        return flag;
    }

    /**
     * 462 / 469
     * "aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga"
     * @param c
     * @return
     */
    public static boolean error_own_validPalindrome(String c) {
        int i=0;
        int j=c.length()-1;
        boolean flag=true;
        int delcount=0;
        while (i<=j&&delcount<=1)
        {
            char ci=c.charAt(i);
            char cj=c.charAt(j);
            if(ci==cj){
                i++;
                j--;
            }else {
                delcount++;
                if(c.charAt(i+1)!=cj)
                {
                    if(c.charAt(j-1)==ci)
                    {
                        i++;
                        j--;
                        j--;
                    }else {
                        return false;
                    }
                }else {
                    i++;
                    i++;
                    j--;
                }
            }
        }
        if(delcount>1)
            return false;
        return flag;
    }
}
